package quwei;

import java.util.Scanner;

public class Test3_3 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入数列中的元素个数n为：");
        int n=scanner.nextInt();
        System.out.println("请依次输入数列中的元素：");
        int[] A=new int[n];
        for(int i=0;i<n;i++)
            A[i]=scanner.nextInt();
        mergeSort(A,0,n-1);

        System.out.println("合并排序的结果：");
        for(int i=0;i<n;i++)
            System.out.print(A[i]+" ");
    }

    /*递归的合并排序算法*/
    public static void mergeSort(int[] A,int low,int high) {
        if(low<high) {
            int mid=(low+high)/2;
            mergeSort(A,low,mid);                             //对A[low...mid]中的元素合并排序
            mergeSort(A,mid+1,high);                          //对A[mid+1...high]中的元素合并排序
            merge(A,low,mid,high);                            //合并操作
        }
    }

    public static void merge(int[] A,int low,int mid,int high) {
        int[] B=new int[A.length];                            //辅助数组
        int i=low,j=mid+1;                                    //i,j分别指向两个待合并子序列中当前待比较的元素
        int k=0;                                              //k指向辅助数组待放置元素的位置
        while(i<=mid&&j<=high) {
            if(A[i]<=A[j])                                    //按从小到大顺序放入B数组中
                B[k++]=A[i++];
            else
                B[k++]=A[j++];
        }

        while(i<=mid)
            B[k++]=A[i++];                                    //对子序列A[low...mid]剩余的元素进行处理
        while(j<=high)
            B[k++]=A[j++];                                    //对子序列A[mid+1...high]剩余的元素进行处理

        for(i=low,k=0;i<=high;i++)
            A[i]=B[k++];                                        //将合并后的序列存放回原数组
    }
}